// 邻接表存储图的拓扑排序
#include<stdio.h>
#include<stdlib.h>
using namespace std;
#define maxsize 100
typedef struct Enode{
    int adjvex;
    struct Enode *next;
}*en;
typedef struct Vnode{
    char data;
    int indegree;
    struct Enode *firstArc;
}*vn,adjList[maxsize];
typedef struct AGraph{
    int vNum,eNum;
    adjList vertices;
}Graph;
void createGraph(Graph *g){
     int i,j,k;
    printf("\n请输入顶点个数和边的条数:");
    scanf("%d %d",&g->vNum,&g->eNum);
    printf("\n请输入顶点信息:");
    for(k=0;k<g->vNum;k++){
        getchar();
        scanf("%c",&g->vertices[k].data);
        g->vertices[k].indegree=0;
        g->vertices[k].firstArc=NULL;
    }
    printf("\n请输入边的信息:\n");
    for(k=0;k<g->eNum;k++){
        scanf("%d %d",&i,&j);
        en enode=(en)malloc(sizeof(struct Enode));
        enode->adjvex=j;
        g->vertices[j].indegree++;
        enode->next=g->vertices[i].firstArc;
        g->vertices[i].firstArc=enode;
        // 无向图省略
    }
}
void printAdjList(Graph g){
    for(int i=0;i<g.vNum;i++){
        printf("%c(入度:%d)->",g.vertices[i].data,g.vertices[i].indegree);
        en p=(en)malloc(sizeof(struct Enode));
        p=g.vertices[i].firstArc;
        while(p){
            printf("%c(入度:%d)->",g.vertices[p->adjvex].data,g.vertices[p->adjvex].indegree);
            p=p->next;
        }
        printf("\n");
    }
}
bool tag[maxsize]={false};
void dfsTuopuSort(Graph g){
    for(int i=0;i<g.vNum;i++){
        if(!tag[i] && g.vertices[i].indegree==0){//寻找入度为0并且没有进行过拓扑排序的顶点
            printf("%c->",g.vertices[i].data);
            tag[i]=true;
            for(en p=g.vertices[i].firstArc;p!=NULL;p=p->next){
                g.vertices[p->adjvex].indegree--;
            }
            dfsTuopuSort(g);
        }
    }
}


void topo(Graph g){
    for(int i==0;i<g.vNum;i++){
        if(!tag[i]&&g.indegree==0){
            printf("%c->",g.vertices[i].data);
            tag[i]=true;
            for(en p=g.vertices[i].firstArc;p;p=p->next){
                g.vertices[i].indegree--;
            }
            topo(g);
        }
    }
}
void dfs(Graph g,int v){
    tag[v]=true;
    for(en p=g.vertices[v].firstArc;p!=NULL;p=p->next){
        if(!tag[p->adjvex]){
            dfs(g,p->adjvex);
        }
    }
    printf("%c->",g.vertices[v].data);
}
void reverse_dfsTuopuSort(Graph g){
    for(int i=0;i<g.vNum;i++){
        tag[i]=false;
    }
    for(int i=0;i<g.vNum;i++){
        if(!tag[i]){
            dfs(g,i);
        }
    }
}

// 判断是否存在环的情况下的逆拓扑排序
bool flag=false;
bool visited[maxsize]={false};//全局访问标记函数
bool nowVisited[maxsize]={false};//单次循环访问标记数组
int count=0;
char print[maxsize];
void DFS(Graph g,int v){
    if(flag==1) return;//存在回路，逐层返回
    visited[v]=true;
    nowVisited[v]=false;    
    for(en p=g.vertices[v].firstArc;p!=NULL;p=p->next){
        if(!visited[p->adjvex]){//这是全局的访问标记数组
            nowVisited[p->adjvex]=true;//将v指向的结点w的nowVisited[]都设置为ture 
            DFS(g,p->adjvex);
        }
    }
    if(nowVisited[v])   flag=1;//说明在本次递归过程中又访问到了v
    print[count++]=g.vertices[v].data;
}

void ABC(Graph g,int v){
    if(flag==1) return;//存在回路直接返回
    visited[v]=true;
    nowVisited[v]=true;
    for(en p=g.vertices[v].firstArc;p!=NULL;p=p->next){
        if(!visited[v]){
            nowVisited[v]=true;
            ABC(g,p->adjvex);
        }
    }
    if(nowVisited[v]) flag=1;//本轮又访问到了v，说明存在回路
    print[count++]=g.vertices[v].data;
}
void DFSTraverse(Graph g){
    // visited[]，nowVisited[]数组也可以在这里初始化
    for(int i=0;i<g.vNum;i++){
        visited[i]=false;
        nowVisited[i]=false;
    }
    for(int i=0;i<g.vNum;i++){
        if(!visited[i])
            DFS(g,i);
    }
    if(flag==1){
        printf("\n有回路，无法输出逆拓扑!\n");
    }else{
        printf("\ndfs实现逆拓扑排序为:\n");
        for(int i=0;i<g.vNum;i++){
            printf("%c->",print[i]);
        }
    }
}

// void dfs_topo(Graph g,int v){
//     visited[v]=true;
//     nowVisited[v]=false;
//     for(en p=g.vertices[v].firstArc;p!=NULL;p=p->next){
//         if(!visited[p->adjvex]){
//             nowVisited[p->adjvex]=true;
//             dfs_topo(g,p->adjvex);
//         }
//     }
// }
// void topoSort(){
//     for(int i=0;i<g.vNum;i++){
//         visited[i]=false;
//         visited[i]=true;
//     }
//     for(int i=0;i<g.vNum;i++){
//         if(!visited[i])
//             dfs_topo(g,i);
//     }
//     if(flag)
//         printf("\n存在回路,无法输出拓扑序列！\n");
//     else{
//         printf("\n拓扑序列为:\n")
//         for(int i=0;i<g.vNum;i++){
//             printf("%d->",print[i]);
//         }
//     }
// }
int main(){
    Graph g;
    createGraph(&g);
    printAdjList(g);
    printf("\ndfs实现拓扑排序如下:\n");
    dfsTuopuSort(g);
    // reverse_dfsTuopuSort(g);
    DFSTraverse(g);
    return 0;
}
